\documentclass[a4paper,11pt,oneside, titlepage]{article}
\author{Groep 13: Sibrand Staessens en Sibren Polders}
\title{Trimesteroverschrijdend Project: Curve Editor}
\date{Dinsdag 10 juni, 2008}
\usepackage[dutch]{babel}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue,filecolor=magenta]{hyperref}
\usepackage{url}
\parindent 0pt
\hyphenation{Hermite deze Monitor-Pool controle-punten Fool-proof}
\fontfamily{times}
\begin{document}
\maketitle \newpage
\tableofcontents \newpage
\section{Voorwoord}
Op welke manieren kan je een set van punten op een vloeiende wijze met elkaar verbinden en hoe ziet het bekomen pad er dan uit ? Dat is
de vraag waarvoor Curve Editor een gedeeltelijke oplossing biedt. Het meest voor de hand liggende pad dat tussen de punten getekend kan worden 
is uiteraard dat pad dat bekomen wordt m.b.v. lineaire interpolatie. Maar er zijn nog zoveel andere mogelijkheden, waarvan er in Curve Editor twee verwerkt 
zijn (nl. B\'ezier- en Hermite-curves). Deze algoritmes zullen in vgl. met lineaire interpolatie vloeiende krommen
tussen de interpolatiepunten cre\"eren. De toepassingen van de door Curve Editor gebruikte algoritmes beperken zich niet enkel 
tot het tekenen van ``lijntjes'' tussen punten, maar worden bijvoorbeeld ook veelvuldig gebruikt voor vloeiende camerabewegingen of ``AI''-bewegingen in games.
De interpolatie van een gegeven set van controlepunten is een uitgebreide en interessante studie die 
op vele vlakken in de informatica/wiskunde zijn nut kan bewijzen. Curve Editor geeft er de 
basistoepassing van, namelijk die van de wiskundige berekening en grafische voorstelling van de gevraagde curve. \newline \newline \newline \newline
\newline \newline \newline \newline
\begin{center}
\textit{``If the path be beautiful, let us not ask where it leads.''} - Anatole France \newpage
\end{center}
\newpage
\section{Wiskundige voorkennis\label{swv}}
\subsection{Lineaire interpolatie \label{sli}}
\subsubsection{Na\"ieve poging (brute force) \label{snp1}}
Een eerste poging om een lineaire interpolatie te berekenen is die waarbij tussen elk paar van controlepunten
de vergelijking \begin{math}y = mx + b\end{math} wordt uitgerekend.
Hierbij geldt: \begin{math}m = (y_1-y_0)/(x_1-x_0)\end{math}, en b is het
startpunt op de y-as. De grote nadelen van dit algoritme zijn dat er voor iedere nieuwe
pixel opnieuw berekend en getekend moet worden en dat er behoefte is aan een floating-point optelling en 
vermenigvuldiging (vermits m een floating-point getal is).
\subsubsection{DDA-interpolatie (Digital Differential Analyzer) \label{sdda}}
Bij deze methode wordt nog steeds m als een floating-point getal voorgesteld, maar de berekening van
de volgende y-waarde wordt als volgt vereenvoudigd:
\begin{math}
y_{i+1} = m.x_{i+1} + b\newline
= m.(x_i + \Delta x) + b\newline
= m.x_i + m.\Delta x + b\newline
= y_i + m.\Delta x\newline
= y_i + m \textrm{ aangezien } \Delta x = 1 \textrm{ als we 1 pixel verder gaan } \newline
\end{math}
Dit algoritme is duidelijk effici\"enter vermits we een floating-point vermenigvuldiging hebben 
verwijderd. Voor een voorbeeld hiervan: zie figuur \ref{lineair}.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies2/lineair.png}
\caption{Lineair}\label{lineair}
\end{figure}
\subsection{B\'ezier \label{sb}}
Het cubic B\'ezier-algoritme construeert een curve als volgt: per vier opeenvolgende controlepunten wordt een deel van de totale curve berekend.
Die deelcurve start in het eerste controlepunt, in de richting van het tweede, om dan in het vierde controlepunt te eindigen in de richting van het derde. Een volgende 
deelcurve heeft als eerste controlepunt het laatste controlepunt van de vorige deelcurve om alzo C0-continu\"iteit te garanderen.
\subsubsection{Na\"ieve poging (brute force) \label{snp2}}
Bij een eerste poging kunnen we het algoritme implementeren a.h.v. de meetkundige constructie en de parametrische voorstelling van de curve.
Deze is als volgt:\newline
\begin{center}
\includegraphics[scale=0.45]{bezier.png}
\end{center}
Indien we nu voor een eindig aantal t-waarden tussen 0 en 1, de B-waarde berekenen, dan hebben we een eindig aantal punten berekend die op de gevraagde curve
liggen. Gebruiken we nadien lineaire interpolatie om de berekende punten met elkaar te verbinden, dan hebben een eerste benadering van de cubic B\'ezier-curve.
Het spreekt voor zich dat deze implementatie verre van effici\"ent is: voor elke t-waarde moeten we de machten uitrekenen, vermenigvuldigen met de co\"ordinaten van de controlepunten
en daarna alles optellen. Dit is tijdsintensief rekenwerk, daarom is in Curve Editor het incrementeel aloritme, dat in de volgende sectie besproken wordt, ge\"implementeerd.
\subsubsection{Forward differences \label{sfd}}
Deze implementatie is een incrementeel algoritme: de volgende berekening wordt gedaan a.h.v. wat in de vorige berekening werd gevonden. Op deze manier moet men voor elk gevraagd punt niet
helemaal van nul beginnen en minder rekenwerk uitvoeren. Hoe we tot de implementatie komen, gebeurt als volgt:

We evalueren de polynoom in een aantal even ver van elkaar liggende punten. Stel dat we $f(t) = a t^3 + b t^2 + c t + d$ willen evalueren voor de punten $t_0, t_1, ... , t_m$ met $t_{i+1} = t_i + \epsilon$ voor $i = 0, 1, ..., m-1$. Dan bekomen we:
\begin{center}
\includegraphics[scale=0.6]{diff1.png}
\end{center}
We noemen $\Delta f_i$ de voorwaartse differentie. Mer op dat $\Delta f_i$ een 2e-graadspolynoom is, een graad lager dan de originele polynoom. We passen hetzelfde toe voor $\Delta f_i$:
\begin{center}
\includegraphics[scale=0.6]{diff2.png}
\end{center}
En voor $\Delta^2 f_i$:
\begin{center}
\includegraphics[scale=0.6]{diff3.png}
\end{center}
Samengevat hebben we dus:
\begin{center}
\includegraphics[scale=0.6]{diff4.png}
\end{center}
We moeten de startwaarden berekenen m.b.v. $t_0 = 0$:
\begin{center}
\includegraphics[scale=0.6]{diff5.png}
\end{center}
Nu hebben we alles wat we nodig hebben, en kunnen we de interpolatiepunten z\'elf gaan berekenen als volgt:
\begin{center}
\includegraphics[scale=0.6]{diff6.png}
\end{center}
\subsubsection{C0-continu\"iteit \label{sc0}}
C0-continue curves zijn de standaard curves, vermits C0-continu\"iteit enkel de eis oplegt dat de curve ononderbroken moet zijn.
Indien we als eerste controlepunt van een viertal het laatste controlepunt van het vorige viertal nemen, dan bekomen we automatisch C0-continu\"iteit. Deze eis vraagt dus geen veranderingen aan de controlepunten: het primitieve
B\'ezier-algoritme voldoet (zie figuur \ref{bezierC0}).
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{./screenies2/bezierC0.png}
\caption{B\'ezier, C0-continu}\label{bezierC0}
\end{center}
\end{figure}
\subsubsection{G1-continu\"iteit \label{sG1}}
G1-continu\"iteit eist dat de curves naast ononderbroken ook overal vloeiend ogen. Dit wordt dus bekomen door in elk controlepunt dat op de curve komt te liggen, de curve z\'o te berekenen dat de ingaande en de uitgaande raakvector
in dat controlepunt op \'e\'en lijn liggen (zie figuur \ref{bezierG1}). In Curve Editor is dit opgelost als volgt:

De ligging van het tweede en het derde controlepunt van een viertal B\'ezier-controlepunten wordt herberekend, zodanig dat de berekende curve vloeiend aansluit op de berekende curve voor het vorige en het volgende viertal. Stel het viertal v1 en viertal v2 opeenvolgende viertallen van controlepunten. Het laatste controlepunt van v1 en het eerste controlepunt van v2 zijn logischerwijs dezelfde: anders zouden we niet tot een aaneengesloten curve kunnen komen (zie C0-continu\"iteit). M.b.v. het voorlaatste controlepunt van v1, het gemeenschappelijke controlepunt en het tweede controlepunt van v2 berekent Curve Editor nu een nieuw voorlaatste controlepunt voor v1 en een nieuw tweede controlepunt voor v2 (het gemeenschappelijke blijft ongewijzigd). Dit doet het door de vector tussen het voorlaatste controlepunt van v1 en het tweede controlepunt van v2 te beschouwen; die vector wordt dan zodanig verschoven dat het gemeenschappelijke controlepunt op die vector komt te liggen. De twee uiteinden van deze verschoven vector zijn dan het nieuwe voorlaatste controlepunt voor v1 en het nieuwe tweede controlepunt voor v2. Indien we nu op die manier voor elk gemeenschappelijk controlepunt twee nieuwe controlepunten berekenen, dan bekomen we een mooi vloeiende curve.
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{./screenies2/bezierG1.png}
\caption{B\'ezier, G1-continu}\label{bezierG1}
\end{center}
\end{figure}
\subsubsection{C1-continu\"iteit \label{sC1}}
C1-continu\"iteit eist dat de curves naast de vereisten voor G1-continu te zijn, ook nog eens in elk controlepunt een gelijkmatig toe- en afnemende kromming hebben. Dit wordt dus bekomen door in elk controlepunt dat op de curve komt te liggen, de curve z\'o te berekenen dat de ingaande en de uitgaande raakvector
in dat controlepunt op \'e\'en lijn liggen \'en even groot zijn (zie figuur \ref{bezierC1}). In Curve Editor is dit opgelost als volgt:

De ligging van het tweede en het derde controlepunt van een viertal B\'ezier-controlepunten wordt herberekend, zodanig dat de berekende curve vloeiend aansluit op de berekende curve voor het vorige en het volgende viertal \'en zodanig dat de berekende curve een controlepunt even snel "binnenkomt" als "verlaat", met dezelfde versnelling als het ware. Stel het viertal v1 en viertal v2 opeenvolgende viertallen van controlepunten. Het laatste controlepunt van v1 en het eerste controlepunt van v2 zijn logischerwijs dezelfde: anders zouden we niet tot een aaneengesloten curve kunnen komen (zie C0-continu\"iteit). M.b.v. het voorlaatste controlepunt van v1, het gemeenschappelijke controlepunt en het tweede controlepunt van v2 berekent Curve Editor nu een nieuw voorlaatste controlepunt voor v1 en een nieuw tweede controlepunt voor v2 (het gemeenschappelijke blijft ongewijzigd). Dit doet het door de vector tussen het voorlaatste controlepunt van v1 en het tweede controlepunt van v2 te beschouwen; die vector wordt dan zodanig verschoven dat het gemeenschappelijke controlepunt midden op die vector komt te liggen. De twee uiteinden van deze verschoven vector zijn dan het nieuwe voorlaatste controlepunt voor v1 en het nieuwe tweede controlepunt voor v2. Indien we nu op die manier voor elk gemeenschappelijk controlepunt twee nieuwe controlepunten berekenen, dan bekomen we een mooi vloeiende en een in elk controlepunt even snel ingaand als uitgaand versnellende curve.
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{./screenies2/bezierC1.png}
\caption{B\'ezier, C1-continu}\label{bezierC1}
\end{center}
\end{figure}
\subsection{Hermite}
Het cubic Hermite-algoritme construeert een curve als volgt: 
per twee controlepunten en hun respectievelijke tangens wordt een deel van de curve berekend.
De deelcurve start in het eerste controlepunt, gaat in de richting van zijn tangens om
tenslotte te eindigen in het tweede controlepunt in de richting van zijn tangens. Een voorbeeld hiervan zie je in figuur \ref{hermite}.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies2/hermite.png}
\caption{Hermite}\label{hermite}
\end{figure}
\subsubsection{Na\"ieve poging}
De na\"ieve methode bestaat erin de expliciete vergelijking van een ``cubic spline''
op te lossen, met de opgegeven punten.\newline
Stel hierbij dat het volgende is gegeven:\newline
$p_0 = (x_0,y_0), p_1 = (x_1,y_1), m_0 = (x'_0, y'_0), m_1 = (x'_1, y'_1)$\newline
hierbij zijn $p_0,p_1$ controlepunten en $m_0, m_1$ hun respectievelijke tangenswaarden.\newline
\newline
De bedoeling is nu van in de vergelijking\newline
$P(X) = ax^3 + bx^2 + cx + d \textrm{   (1)}$\newline
a, b, c en d te vinden in functie van de opgegeven punten.\newline

Je weet het volgende:
$y_0 = ax_0^3 + bx_0^2 + cx_0 + d \textrm{   (2)}$\newline
$y_1 = ax_1^3 + bx_1^2 + cx_1 + d \textrm{   (3)}$\newline
(dit volgt rechtstreeks uit het gegeven)\newline

verder is duidelijk dat de tangens van een punt op deze polynoom gelijk is aan de 
eerste afgeleide van de polynoom ge\'evalueerd naar dat punt.\newline

Symbolische afleiding van de polynoom geeft:
$P'(X) = 3ax^2 + 2bx + c$
en dus
$y'_0 = 3a{x'}_0^2 + 2bx'_0 + c \textrm{   (4)}$\newline
$y'_1 = 3a{x'}_1^2 + 2bx'_1 + c \textrm{   (5)}$\newline
(dit volgt weer rechtstreeks uit het gegeven)\newline

Het stelsel opgebouwd uit formules (1) - (4) kan je vervolgens oplossen naar a, b, c en d
om het volgende te krijgen:\newline

$a = {{{-{x_1}^2y'_0+x'_0y_1+x'_1x_1y'_0-x'_1y_1+{x_1}^2y'_1-x'_1x_0*y'_0+{x_0}^2y'_0+x'_1y_0-{x_0}^2y'_1-x_1x'_0y'_1+x_0x'_0y'_1-x'_0y_0}}\over{-x'_1{x_1}^3+x'_1x_1*{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0*{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline \newline

$d = {-{{x'_0}^2y_0{x_1}^2-{x'_0}^2y_0*{x'_1}x_1-{x'_0}^2{x_0}^2y_1-x_0{x'_0}^2{x_1}^2y'_1+x_0{x'_0}^2x'_1y_1+{x'_0}^2{x_0}^2x_1y'_1+x'_0{x'_1}^2y_0x_1\over{-x'_1{x_1}^3+x'_1*x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}}$\newline \newline
${{x'_0x_0y'_1{x_1}^3-x_0{x'_1}^2x'_0y_1+x'_0{x_0}^3y_1-x'_0{x_0}^3x_1y'_1-x'_0y_0{x_1}^3-x'_1x_0y'_0{x_1}^3}\over{-x'_1{x_1}^3+x'_1*x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline \newline

${{-{x_0}^3{x_1}^2y'_0+{x'_1}^2{x_0}^2y_1-{x'_1}^2{x_0}^2x_1y'_0-{x_0}^2y'_1{x_1}^3+x'_1y_0{x_1}^3+{x_0}^2y'_0{x_1}^3+{x_0}^3x'_1x_1y'_0-y_0{x_1}^2{x'_1}^2+x_0{x'_1}^2{x_1}^2y'_0-x'_1{x_0}^3y_1+{x_0}^3{x_1}^2y'_1}\over{-x'_1{x_1}^3+x'_1*x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline \newline

$b = {-{{x'_0}^2y_1-{x'_0}^2x_1y'_1+{x'_0}^2x_0y'_1-{x'_0}^2y_0-{x_0}^3y'_1+y'_0x_1{x'_1}^2-{x'_1}^2y_1+{x'_1}^2y_0-y'_0{x_1}^3+{x_0}^3y'_0+y'_1{x_1}^3-y'_0x_0{x'_1}^2}\over{-x'_1{x_1}^3+x'_1x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline \newline

$c = $\newline
${{-y'_0x'_1{x_1}^3-y'_1x'_0{x_0}^3+{x'_0}^2x'_1y_1-{x'_0}^2{x_1}^2y'_1-{x'_0}^2x'_1y_0+{x'_0}^2{x_0}^2y'_1+{x'_1}^2{x_1}^2y'_0-{x'_1}^2x'_0y_1}\over{-x'_1{x_1}^3+x'_1x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline
${{-{x'_1}^2{x_0}^2y'_0+{x'_1}^2x'_0y_0+y'_0x'_1{x_0}^3+y'_1x'_0{x_1}^3}\over{-x'_1{x_1}^3+x'_1x_1{x'_0}^2+x'_0{x_1}^3-{x_1}^2{x'_0}^2+{x_1}^2{x'_1}^2-x_1x'_0{x'_1}^2+x'_1{x_0}^3-x'_1x_0{x'_0}^2-x'_0{x_0}^3+{x_0}^2{x'_0}^2-{x_0}^2{x'_1}^2+x_0x'_0{x'_1}^2}}$\newline

Om de interpolatie te kunnen doen moet je tussen elke 2 controlepunten a, b, c en d invullen
zodat je deze in formule (1) kan invullen. Deze formule stelt dan juist de interpolatie 
voor die je wilt verkrijgen. Door de x in formule (1) dan te laten vari\"eren tussen 
$x_0$ en $x_1$ met een bepaalde stapgrootte kan je de lijn pixel per pixel berekenen.
\subsubsection{M.b.v. basisfuncties}
Een betere methode om de Hermite-polynoom te berekenen dan degene hierboven vermeld, is gebruik te maken van de vier eerste Hermite-basisfuncties en de polynoom parametrisch op te schrijven.

De formule om deze berekening te kunnen uitvoeren is:\newline \newline
$P(t) = h_{00}p_0 + h_{10}m_0 + h_{01}p_0 + h_{11}m_1 \textrm{   (1)}$\newline \newline
met\newline \newline
$h_{00} = 2t^3 - 3t^2 + 1\ \textrm{   (2)}$\newline
$h_{10} = t^3 - 2t^2 + t\ \textrm{   (3)}$\newline
$h_{01} = -2t^3 + 3t^2\ \textrm{   (4)}$\newline
$h_{11} = t^3 - t^2\ \textrm{   (5)}$\newline

In deze formule zijn $h_{00}$ tot $h_{11}$ de Hermite-basisfuncties, $p_0$, $p_1$ 
de controlepunten en $m_0$, $m_1$ hun respectievelijke tangenswaarden. t gaat hier van 0 tot 1.

Zo sla je het berekenen van a, b, c en d over en zal de curve vloeiender lijken vermits je
met een parametrisch beschreven polynoom werkt.
\subsubsection{Forward differences}
De forward differences-methode is al gedetailleerd beschreven in een voorgaande
sectie bij B\'ezier. Om deze methode met Hermite te implementeren dien je enkel
de volgende berekeningen te maken:\newline \newline
$a = 2p_1 + t_1 - 2p_2 + t_2$\newline
$b = -3p_1 - 2t_1 + 3p_2 - t_2$\newline
$c = t_1$\newline
$d = p_1$\newline \newline

Deze waardens voor a, b, c en d volgen uit de formule die je krijgt waneer je in formule 1 van de voorgaande sectie formules 2-4 invult.
Als we dan de bekomen waarden a, b, c en d invullen in de formules verkregen in de sectie
over forward differences bij B\'ezier, dan krijgen we net dat wat we nodig hadden. Namelijk
forward differences-formules voor een Hermite-polynoom.
\subsubsection{Hermite - Cardinal}
De methode van punten berekenen is hier net hetzelfde als besproken in de voorgaande secties
Met dat verschil dat de tangenswaarden nu niet meer expliciet gegeven dienen te worden, maar 
berekend worden uit de opgegeven controlepunten. 
De tangens wordt door de volgende formule uitgerekend:\newline 
$m_k = (1 - c)(p_{k+1} -p_{k-1})/2$

Hierbij is c een willekeurig getal tussen 0 en 1.

Uit deze formule is duidelijk af te leiden dat er geen lijn getrokken kan worden 
tussen het eerste en het tweede controlepunt en het voorlaatste en het laatste controlepunt, omdat hun tangens niet uit deze formule afgeleid kan worden. Deze tangens is noodzakelijk
om de verdere berekeningen te volbrengen. (zie figuur \ref{cardinal})
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.4]{./screenies2/cardinal.png}
\caption{Hermite - Cardinal}\label{cardinal}
\end{center}
\end{figure}
\subsubsection{Hermite - Catmull-Rom}
Deze methode komt volledig overeen met de methode van Cardinal, met het enige verschil dat
de toen random gekozen waarde c nu altijd 0.5 is. Om dezelfde reden kan er weer geen curve getrokken
worden tussen het eerste en het tweede punt en het laatste en voorlaatste punt. (zie figuur
\ref{catmull})
\begin{figure}[htbp]\
\begin{center}
\includegraphics[scale=0.4]{./screenies2/catmull.png}
\caption{Hermite - Catmull-Rom}\label{catmull}
\end{center}
\end{figure}
\subsubsection{Hermite - Kochanek–Bartels}
Deze methode maakt weer gebruik van het normale Hermite-algoritme. Het verschil
met de 2 voorgaande berekeningen is dat Kochanek-Bartels rekening houdt met start- en eind-
tangenswaarden.

Deze methode maakt gebruik van 3 variabelen:\newline
t = tension (verandert de lengte van de tangens)\newline
b = bias (verandert de richting van de tangens)\newline
c = continu\"iteit (controleert de gladheid van de overgang tussen begin- en eind-tangenswaarde)
\newline

Al deze variabelen vari\"eren tussen -1 en 1, hoe dichter de variabelen bij -1 zitten hoe
meer de curve lineariteit benadert. Als de variabelen dicht bij de 1 zitten dan zal de curve
gladder zijn.\newline

De formules om de tangens te berekenen zijn (hierbij is m0 de tangens van p0 en m1 de tangens
van p1):\newline
$m0 = {{(1-t)(1+b)(1-c)(p_i-p_{i-1})}\over{2}} + {{(1-t)(1+b)(1+c)(p_{i+1}-p_i)}\over{2}}$\newline
$m1 = {{(1-t)(1+b)(1+c)(p_i-p_{i-1})}\over{2}} + {{(1-t)(1+b)(1-c)(p_{i+1}-p_i)}\over{2}}$\newline

Dus bij input van vier controlepunten kan je de tangens van controlepunt het tweede en derde
punt berekenen. Net zoals bij de vorige algoritmes zal je dus niet kunnen interpoleren tussen
de eerste en de tweede controlepunten en de voorlaatste en de laatste controlepunten.
\newpage
\section{Implementatie}
\subsection{Packages}
\subsubsection{Java packages}
Een Java package is een mechanisme binnen Java om klassen te organiseren in namespaces. 
Java broncode die binnen eenzelfde categorie of functie vallen kunnen hierdoor gegroepeerd 
worden. Dit kan door middel van een package statement bovenaan het beginbestand om aan te 
geven waartoe ze behoren. Dit is omwille van twee redenen handig: de klassen zijn dan gegroepeerd
in functionele categorie\"en, wat het geheel overzichtelijker maakt. En verder kunnen er nu twee 
verschillende klassen \'e\'enzelfde naam krijgen en toch uniek bepaald worden door er zijn
package name voor te zetten. Dit is zeker handig als de programmeur een klasse dezelfde naam
heeft gegeven als een klasse uit een library die hij wilt gaan gebruiken.\newline \newline
Voor Curve Editor zijn verschillende packages gemaakt, die zijn te zien op figuur \ref{iTot}.
In wat volgt wordt een korte beschrijving gegeven van al deze packages, zonder \'al teveel op de technische details in
te gaan.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{./UML2/Total.png}
\caption{Totaal diagram}\label{iTot}
\end{figure}
\subsubsection{CurveEditor}
Dit is wellicht de kleinste package van de reeks. Het bevat slechts \'e\'en klasse, 
namelijk die klasse die de main-methode bevat. Deze klasse zal, zoals wellicht duidelijk is, als bootstrap dienen voor Curve Editor. 
Er wordt ook de mogelijkheid geboden om rechtstreeks vanuit
de command line een bestand mee te geven. Dit is enkel ter volledigheid, vermits de gebruiker in de applicatie zelf zeer makkelijk bestanden kan inladen en opslaan.
\subsubsection{Algorithms}
Een volgend pakket voorziet de verschillende klassen die voor de interpolatiealgoritmen zullen zorgen.
Elke klasse in dit pakket implementeert de Algorithm-interface. Dit is handig voor latere uitbreidingen en groepswerk: deze interface 
legt immers vast welke functies de programmeur zal moeten implementeren. Deze ``vaste'' functies worden dan elders in de applicatie gebruikt. \newline
De klassenamen zijn triviaal gekozen: ``Lineair, Bezier, BezierC1, BezierG1, Hermite, 
HermiteCardinal, HermiteCatmullRom'' (zie figuur \ref{iAlg}).
Zoals de namen al doen vermoeden, zullen deze klassen de verschillende
interpolatiemethodes besproken in het deel 'Wiskundige voorkennis' (\ref{swv}) implementeren.
Hierbij werd natuurlijk altijd geopteerd voor de meest optimale implementatie van degene die 
besproken werden.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.45]{./UML2/Alg.png}
\caption{Algorithm}\label{iAlg}
\end{figure}
\subsubsection{Core}
\label{tcore}
Dit pakket bevat enkele noodzakelijk klassen (zie figuur \ref{iCore}).\newline \newline
De klasse CurveContainer zal ervoor zorgen dat ingegeven punten kunnen opgeslagen worden, samen
met hun door interpolatie berekende punten. \newline \newline
Een eerste implementatie gebruikte het subdivision principe. In de beginsituatie is het tekenveld
dan \'e\'en grote rechthoek. Van zodra de gebruiker een curve begint te tekenen worden de secties,
waar nieuwe punten geplaatst zijn, onderverdeeld in steeds kleiner wordende rechthoekjes. In elk zo'n
rechthoekje zat dan juist \'e\'en punt van een curve. Nagaan welke curve op een bepaalde pixel lag, was op deze manier
makkelijk te achterhalen m.b.v. een quadtree.\newline
Deze implementatie bleek echter niet zo effici\"ent te zijn wanneer we te maken hadden met een groot
aantal controlepunten. Dit kwam voornamelijk doordat er telkens opnieuw kleinere rechthoekjes
moesten aangemaakt worden bij het ingeven van een nieuw punt, en een grotere wanneer er punten verwijderd
werden. Uiteindelijk was de applicatie meer bezig met het bepalen van rechthoekjes dan met zijn
doel: bijhouden en picken van curves. De gebruike datastructuur gaf wel mooie resultaten voor het zoeken van curves a.h.v.
een geklikt of gehooverd punt, maar wanneer de gebruiker de curves ging aanpassen (nieuwe punten, verplaatsen, connecteren, \ldots), dan ging de 
herberekening en aanpassing van de datastructuur echter tergend langzaam. Wij achtten het dan ook noodzakelijk dat we een andere manier
zouden vinden, die een betere balans tussen "aanpassen" en "informatie halen uit". \newline \newline
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{./UML2/Core.png}
\caption{Core}\label{iCore}
\end{figure}
De tweede door ons ge\"implementeerde datastructuur leek ons direct bruikbaarder. Het aanpassen van de datastructuur ging immers direct een pak sneller in vgl.
met de vorige implementatie, de gebruiker kan nu bvb. redelijk vlug nieuwe controlepunten vlak achter elkaar ingeven. Ook het halen van informatie uit de datastructuur heeft een aanvaardbare snelheid.
Wat stelt die datastructuur nu precies voor ? We stellen een tweedimensionale matrix op waarvan elk element een referentie kan bevatten naar een curve-instantie.
Het toevoegen van curves is op deze manier zeer simpel te doen: voor elk punt van de curve plaatsen we in de overeenkomstige cel van de matrix een referentie naar de curve.
Curves verwijderen is dan gewoon het tegenovergestelde: al die cellen weer naar null laten wijzen. Het zoeken naar een curve a.h.v. een punt (a.h.v. co\"ordinaten van een muisevent, bijvoorbeeld) 
gaat nog vrij snel omdat we enkel maar in een bepaalde range in de matrix de inhoud van de cellen moeten bekijken. Indien een niet-null referentie in die range aanwezig is, dan weten we welke curve
daar ligt.\newline \newline
De klasse Editor is het hart van Curve Editor. Deze zal zorgen dat gegevens tussen de verschillende datastructuren (Point, Curve, Algorithm) kan doorgegeven worden.
De uitwisseling van data zal voornamelijk bestaan uit het zoeken/verwijderen van punten uit de CurveContainer-klasse en het veranderen van Curves (verplaatsen, punten toevoegen/verwijderen, type veranderen, \ldots).
Maar ook het opvangen en afhandelen van excepties gebeurt grotendeels in Editor. Deze klasse zorgt er m.a.w. voor dat de 
verschillende andere klassen zo autonoom mogelijk kunnen werken, Editor is dan de klasse die alles samenbrengt. Dit verhoogt natuurlijk ook de leesbaarheid en onderhoudbaarheid van de code.\newline \newline
Een laatste klasse van dit pakket is de FileIO-klasse, deze zal niet alleen bestanden opslaan en
inladen, maar ook zal hij de undo/redo-functionaliteit verzorgen, vermits deze van
dezelfde functies gebruik maakt. Er wordt dan gewoon een stack van bestanden in het geheugen bijgehouden.
\subsubsection{Curves}
Dit pakket bevat de twee datatypes die doorheen het programma gebruikt worden (zie figuur \ref{iCurv}). Point verzorgt, zoals
de naam doet vermoeden, de datastructuur die punten voorstelt. Curve geeft dan weer de
mogelijkheid om een verzameling van punten (lees: een kromme of curve) op te slaan. De
technische details van deze laatste klasse worden beter uitgelegd verder in de tekst. 
Voorlopig is het voldoende om te weten dat Curve een vector van Point-instanties bijhoudt en enkele
basisvoorzieningen voorziet (punten opvragen, toevoegen, transleren, \ldots).
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{./UML2/Gen.png}
\caption{Curves (ADT's + interacties daartussen)}\label{iCurv}
\end{figure}
\subsubsection{Exceptions}
Een foutloos programma schrijven is op zich al een opgave, vermits er altijd wel kleine bugs
kunnen opduiken na langdurig en gevari\"eerd gebruik. Foolproof code schrijven daarentegen is een
onmogelijke opgave. Daarom hebben we gebruik gemaakt van exceptions om ``verkeerd'' gebruik van
CurveEditor-functies op te vangen (zie figuur \ref{iExc}). Onder verkeerd gebruik valt bijvoorbeeld het inladen van een
onbestaande file of een verkeerd bestandsformaat, het toevoegen van een punt zonder er de 
co\"ordinaten van op te geven, \ldots. Maar ook met toekomstige uitbreidingen in gedachte zijn exceptions een handig middel,
niet elke programmeur hanteert immers dezelfde logica. 
Er zijn ook twee HandleException-klassen voorzien (zie figuur \ref{iHExc}): eentje in dit pakket, deze zal gewoon 
het exceptie bericht in de console uitprinten, en eentje in het GUI-pakket, die in een dialoogvenstertje de exceptie zal uitprinten.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./UML2/HandleExc.png}
\caption{HandleExceptions}\label{iHExc}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./UML2/Exc.png}
\caption{Exceptions}\label{iExc}
\end{figure}
\subsubsection{GUI}
Een volgend pakket dat voor de gebruiker het belangrijkste is, daar deze er het resultaat van "ziet", is de GUI. De GUI is vrij grondig opgesplitst (zie figuur \ref{iGui}). Elk groot deel heeft zo zijn eigen klasse; 
zo heb je een menubalk-klasse, een snelknopbalk-klasse, een tekengebied-klasse en een keuzegebied-klasse. \newline
De GUI-klasse zal op zijn beurt het centrale orgaan spelen die al deze klassen met elkaar verbindt.
Het is daarom ook logisch dat deze is afgeleid van de klasse Editor,
de centrale klasse van de Core-package. Zo kunnen immers Core-functionaliteiten aan GUI-events e.d. gelinkt worden.
\newline
Het opdelen van de GUI in verschillende klassen heeft enorme voordelen als we spreken 
over leesbaarheid en onderhoudbaarheid van code. Het EventHandling-systeem van Java zelf is overigens
optimaal voor dit soort afscheiding. In Java worden de events immers opgevangen in een klasse,
die afgeleid wordt van een van de Listener-interfaces (ActionListener, ItemListener, \ldots). Deze 
klasse zal dan de door de interface opgelegde functies impementeren om alzo de juiste evenafhandeling te kunnen
doen. Het is dus voldoende om deze EventHandling-klassen in GUI aan te maken en door te geven
aan de juiste componenten (menubalk, tekengebied, \ldots). Meer uitleg hierover vind je verder in
de tekst. Het eindresultaat van de GUI kan je aanschouwen in figuur \ref{GUI}.
In de bijlage vind je ook een vroeg model van de GUI (figuur \ref{mockup}), m.a.w. de mock-up.
Ook is er een leeg applicatievenster (figuur \ref{start}) en een aangeduid applicatievenster (figuur \ref{scrTot}) toegevoegd
om zo de opbouw van de GUI wat te verduidelijken
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./UML2/GUI.png}
\caption{GUI}\label{iGui}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies/hooverCurve.jpg}
\caption{GUI}\label{GUI}
\end{figure}
\subsubsection{Tools}
Tenslotte bevat dit laatste pakket een curvesimulator (zie figuur \ref{iTools}). In principe is het een ``chique'' naam voor een bolletje
dat over het pad dat de curve voorstelt loopt. Dit kan bijvoorbeeld door de gebruiker gebruikt worden om de stijging en daling
van de curve te bestuderen. Zodoende kan hij de getekende curve visueel evalueren.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{./UML2/Path.png}
\caption{Path Simulation Tool + interactie met DrawArea}\label{iTools}
\end{figure}\newpage
\subsection{Uitwerking van de GUI}
\subsubsection{Overzicht}
Zoals in figuur \ref{scrTot} te zien is kan de vormgeving van de GUI in 4 grote stukken worden opgedeeld:
\begin{enumerate}
\item Menubalk\newline
Hierin kan de gebruiker elke actie terugvinden die door Curve Editor kan gedaan worden.
Bijna elke actie is ook aan te roepen met behulp van sneltoetscombinaties ( Alt-F, Ctrl-O, \ldots ), zodat
elke gebruiker op zijn favoriete manier kan navigeren doorheen de verschillende uitvoerbare taken.
Er is overigens aandacht geschonken aan de nesting van de menu-items: die mogen noch te diep noch te breed zijn.

Verder is elke naam zo triviaal mogelijk gekozen en meestal wordt die ook voorzien van een icoontje (zie figuur \ref{scrMenTo}).
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies/menuTools.jpg}
\caption{Curve Editor-omgeving, Menu - Tools}\label{scrMenTo}
\end{figure}
\item Snelknopbalk\newline
Hierin vind je enkele veelgebruikte taken terug (nieuw bestand beginnen, bestand openen, 
nieuwe curve starten, \ldots). Dit is voorzien opdat de gebruiker deze taken snel en en dus effici\"enter kan
afhandelen dan wanneer hij dat telkens vanuit de menubalk zou moeten doen.
\item Keuzegebied\newline
In dit gebied zal de gebruiker snel kunnen kiezen welk type curve hij wilt tekenen (B\'ezier, 
Hermite, \ldots) en kan hij ten alle tijden een punt aan de op dat moment geselecteerde curves toevoegen door 
de co\"ordinaten in te geven. Verder kan de gebruiker hier ook kiezen of hij de co\"ordinaten, raakvectoren en 
puntnummers van de geselecteerde curves wilt laten uittekenen (zie figuur \ref{scrTot}). \newline
Het Edit-veld van dit gebied hangt af van de mode waarin je bezig bent. Er zijn voor de gebruiker
twee grote modi "voelbaar". De eerste is curve-modus: hier bewerk je de curves op zich (selecteren, 
deselecteren, nieuwe curve maken, \ldots); de tweede is controlepunt-modus (punt verslepen, selecteren, toevoegen).
Naargelang de modus waarin je zit zullen andere mogelijkheden zichtbaar worden in het Edit-veld.
Dit leidt tot een groter gebruiksgemak vermits de taken die verschijnen meestal ook gebruikt
worden wanneer je in die modus werkt.
\item Tekengebied\newline
Dit gebied is waarschijnlijk wel het interessantste voor de gebruiker. Met behulp van muisinteractie
kan de gebruiker controlepunten aan dit veld toevoegen en deze punten laten connecteren
door een interpolatiealgoritme. De gebruiker kan tevens in dit veld punten en curves selecteren,
verwijderen en zelfs verslepen. Het tekengebied maakt gebruik van double buffering om 
beeldflikkering te vermijden en ook van clipping zodat alleen getekend wordt wat ook echt
op het scherm k\'an verschijnen.
\end{enumerate}
\subsection{Listeners in Java }
(zie figuur \ref{iLis})
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./UML2/Listeners.png}
\caption{Event Listeners}\label{iLis}
\end{figure}
Java heeft een aparte stijl om events op te vangen (signalen gestuurd door buttons, menu-items,
\ldots). De taal bezit hiervoor zogenaamde EventListener-interfaces. De programmeur
moet een klasse aanmaken die een dergelijke interface zal implementeren. Deze klasse wordt dan
m.b.v. een simpel commando geconnecteerd met een bepaalde component (bijvoorbeeld een button).
In de interface is er een EventHandle-functie gedefini\"eerd die door de programmeur zal 
ge\"implementeerd worden, zodat, wanneer de component een event genereert,
die opgevangen en afgehandeld kan worden.\newline

Dit systeem is pas echt voordelig als je een event moet afhandelen in een geneste klassestructuur. 
Stel als voorbeeld: je hebt in een klasse A een instantie van een klasse B zitten
die op zijn beurt dan weer een instantie heeft van klasse C, en je wilt dat klasse A een handeling (zie figuur \ref{vb}) doet als klasse C een event uitstuurt.
Met callbacks is de properste manier (om klasse-onafhankelijkheid te bewaren) een callback 
te connecteren van klasse A naar klasse B en daarna een callback van klasse B naar klasse C (zie figuur \ref{call}).
In Java kan je gewoon een EventHandle-klasse vanuit klasse A meegeven aan B die het op zijn 
beurt meegeeft aan klasse C (zie figuur \ref{lis}). Dit maakt de structuur natuurlijk wat eenvoudiger, overzichtelijker, en makkelijker te begrijpen.\newline \newline

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies2/vb.png}
\caption{Object A bevat een Object B dat een Object C bevat}\label{vb}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies2/vbCallbacks.png}
\caption{Informatie uitwisselenen tussen A en C m.b.v. callback functies}\label{call}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies2/vbListeners.png}
\caption{Informatie uitwisselenen tussen A en C m.b.v. Event Listeners}\label{lis}
\end{figure}
In deze implementatie is ervoor gekozen om deze EventHandle-klassen in de klasse GUI te 
defini\"eren. Het voordeel hiervan is dat enkel de klasse GUI de EventHandle-klassen kan 
instanti\"eren en deze instanties zullen alle membervariabelen en -functies van GUI zelf kunnen 
gebruiken. Dit zorgt ervoor dat er geen extra connectie moet gelegd worden tussen de 
EventHandle-klassen en GUI. Je kan dit dus bekijken als een soort van friendly class die niet ge\"instantieerd kan worden.
\subsection{Datastructuren}
(zie figuur \ref{iCurv})
\subsubsection{Point}
Deze datastructuur heeft niet zoveel uitleg nodig, een Point bestaat namelijk uit zijn x- en y-waarde en is daarmee
volledig gedefini\"eerd. De nodige get()- en set()-functies zijn ook voorzien, uiteraard.
\subsubsection{Curve}
Deze structuur heeft al iets meer uitleg nodig. Een curve is, vanuit het laagste niveau bekeken, niets 
anders dan een container van zijn punten.\newline
Elke Curve houdt drie essenti\"ele dingen bij
\begin{enumerate}
\item zijn type (B\'ezier, Hermite, \ldots)
\item een Vector van controlepunten: deze wordt dus gevuld wanneer de gebruiker een nieuw controlepunt aan de curve toevoegt
\item een Vector van outputpunten: deze wordt a.h.v. de Vector van controlepunten en m.b.v. een Algorithm-instantie gevuld
\end{enumerate}

Hierbij worden het type en de controlepunten dus door de gebruiker ingegeven/veranderd. De vector van outputpunten
wordt intern berekend door de verschillende interpolatiealgoritmen. Het aanroepen van deze Algorithm-functies gebeurt niet in Curve, maar in Editor, de klasse die alle datastructuren samenbrengt.
De vectoren worden ook door de GUI gebruikt om de curve op het tekengebied te kunnen uittekenen.\newline

Om de punten op te slaan hebben we voor een Vector gekozen, omdat de verschillende
interpolatietechnieken gemakkelijk moeten kunnen "springen" tussen de gegeven controlepunten om
hun algoritme te kunnen uitvoeren.

Deze klasse bevat ook nog functies om punten te verwijderen, toe te voegen, om na te gaan of een gegeven punt al dan niet tot de curve behoort, \ldots.
\subsection{Extra's}
Bestanden kunnen opgeslaan worden naar meerdere formaten (*.xml en *.gif/*.png), oneindige undo/redo-stack, \ldots  kunnen als extra's beschouwd worden, al zijn het niet meer dan reeds op voorhand te verwachten features van Curve Editor. Voor de rest is er wat aandacht besteed aan het gebruiksgemak: zo zal er bijvoorbeeld tijdens het verslepen van een curve, een grijs pad te zien zijn, selecteren doe je m.b.v. een grijs kader (zie figuur \ref{scrSel}), of door te klikken op een curve. Curves en punten veranderen van kleur naargelang ze geselecteerd, gehoovered of ongeselecteerd zijn (de gebruiker kan deze kleuren zelf bepalen): allemaal kleine dingen die het gebruik toch aangenamer maken.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies/selectPoint.jpg}
\caption{Curve Editor-omgeving, dragging selectietooltje}\label{scrSel}
\end{figure}
\subsubsection{Path Simulation Tool}
Dit tooltje loopt de geselecteerde curves \'e\'en voor \'e\'en af, en laat een bolletje verschijnen dat als het ware "loopt" van het begin naar het einde van de curve. 
De snelheid van het bewegende bolletje zal afhangen van de de ``helling'' waarover hij loopt.
Op een lineair pad zal de snelheid constant blijven, bij krommingen echter zal het bolletje
trager stijgen en sneller dalen. Zodoende kan de gebruiker de resultaten beter interpreteren.
Het starten van deze tool laat een nieuwe thread starten, zodat men \'en de tool kan laten runnen \'en men terwijl de geselecteerde curves zelf nog kan aanpassen (verslepen e.d.). 
\subsection{Interessante problemen}
\subsubsection{Vector vs. LinkedList}
Hoewel de collecties van outputpunten van curves enkel maar sequenti\"eel worden doorlopen (achteraan toevoegen, hele inhoud verwijderen, van voor naar achter uittekenen, \ldots), bleek Vector toch de betere keuze te zijn.
Hoewel de structuur van LinkedList ook zou moeten voldoen, maar met een kleiner geheugenverbruik dan Vector, bleek deze datastructuur tergend langzaam te werken. Een reden hiervoor hebben we niet gevonden, maar door gewoon terug gebruik te maken van Vector was het probleem ook opgelost.
\subsubsection{HashMap vs. 2D Matrix}
Voor de CurveContainer, die de picking moet afhandelen, hadden wij aanvankelijk een HashMap gebruikt. De keys van de HashMap in de bovenste laag waren de pixels/punten van het scherm, en de values waren referenties naar rechthoekjes. Bij initialisatie van de CurveContainer wijzen alle values naar eenzelfde rechthoek. Elk van die rechthoekjes bevat \'e\'en referentie naar een Curve-instantie en een Point-instantie, of twee null-referenties. Zo wordt elk rechthoekje gemapt op een Curve.

Wordt er een extra punt aan de container toegevoegd, dan wordt de rechthoek naarwaar de pixel momenteel verwijst opgesplitst in vier deelrechthoekjes, indien die niet naar null verwijst en indien de resulterende rechthoekjes niet t\'e klein zijn. Indien die wel naar null refereert, dan wordt de hele rechthoek gemapt op die Curve zonder de rechthoek daarvoor op te splitsen, en wordt de Point-referentie gelijkgesteld aan de referentie naar het nieuwe controlepunt. Als er vier deelrechthoekjes aangemaakt dienen te worden, dan wordt voor elk van die rechthoekjes bepaald naar welke Curve zij moeten verwijzen, die van het nieuwe controlepunt, of de Curve waarnaar de grote rechthoek refereerde. Het rechthoekje waarin het nieuwe controlepunt ligt, wordt automatisch aangepast zodat het naar de andere Curve verwijst. Voor de 3 andere wordt de afstand berekend van het middelpunt van het rechthoekje tot het punt naarwaar de Point-instantie van de omkoepelende rechthoek wijst. Is die afstand groter dan de afstand van het middelpunt tot het nieuwe controlepunt, dan zal dat rechthoekje niet de referenties van de omkoepelende rechthoek overnemen, maar naar de nieuwe Curve/Point refereren.
Alle punten in dat rechthoekje wijzen in de HashMap naar dat rechthoekje, uiteraard.

Een curve verwijderen gaat als volgt: men gaat voor alle punten de hashmap af, indien het gevonden rechthoekje naar de curve wijst, dan dient dat rechthoekje aangepast te worden. Als de omliggende rechthoekjes naar eenzelfde curve verwijzen, dan wordt van die vier rechthoekjes weer één rechthoek gemaakt. Indien de omliggende rechthoekjes niet naar eenzelfde curve verwijzen, dan wordt weer de afstand berekend van het middelpunt van het te veranderen rechthoekje tot de punten naarwaar de andere rechthoekjes refereren. Hetgeen de kleinste afstand oplevert, heeft de referenties die men zoekt. 

Een Curve opzoeken gaat razendsnel doordat gewoon in de bovenste HashMap de value voor de key/punt gehaald moet worden. 
A.h.v. het bekomen rechthoekje kan men weten naar welke Curve het punt wijst.

Jammer genoeg ging het telkens aanpassen van de hele rechthoekstructuur zeer langzaam wat tot ergernissen bij de eindgebruiker zou leiden. Het picken ging echter wel h\'e\'el vlug, maar we verkiezen toch een datastructuur die misschien net iets minder vlug is voor picking, maar voor aanpassingen aanvaardbare snelheden geeft.
Een eerste datastructuur die we implementeerden was een simpele Matrix zoals die uitgelegd werd in sectie \ref{tcore}. Die bleek vlot genoeg te werken, dus uiteindelijk hebben we deze datastructuur maar behouden.
\subsubsection{Systeemafhankelijke problemen}
Op de meeste PC's werkt Curve Editor zoals het hoort, maar op sommige systemen blijkt het toch minder performant te werken.

Zo werkt het pixel-tekenen van Curve-Editor op UHasselt-laptops z\'e\'er traag. Dit zal waarschijnlijk te wijten zijn aan slechte Nvidia-drivers, want op diezelfde laptops werkt het in Linux wel vlotjes.
Op andere geteste Windows-systemen doken er geen problemen op.

Een foute configuratie van de Xorg-server in Linux zorgt ook voor problemen. Zo is het op \'e\'en getest systeem onmogelijk Curve Editor te resizen of te verplaatsen. Dat laatste lukt wel, maar het zorgt ervoor dat 
wanneer je dan op menu-items klikt, ze direct terug "wegspringen".
\newpage
\section{Planning}
Hier volgt een beknopte versie van de planning die we hadden opgesteld voor dit project.
De volledige versie is terug te vinden in de appendix.

\begin{itemize}
\item \textbf{11/02/08 - 17/02/08}\newline
Opzoekwerk van de mogelijkheden van Java (Swing, EventListeners, 2D tekenen, \ldots).
\item \textbf{18/02/08 - 24/02/08}\newline
Feedback afwachten en verwerken, samenbrengen van opgezocht materiaal, bespreken
van de mogelijkheden.
\item \textbf{24/02/08 - 02/02/08}\newline
Aanpassingen in de structuur a.h.v. de feedback, exacte taakverdeling opstellen, verdere
taakplanningen opstellen, de gebruikte interfaces opstellen.
\item \textbf{03/03/08 - 23/03/08}\newline
Examens en rustperiode na de examens.
\item \textbf{24/03/08 - 30/03/08}\newline
Besprekingen i.v.m. de GUI, "Waar hoort wat ?", "Wat moet er zeker in staan ?", en een mock-up maken.
\item \textbf{31/03/08 - 06/04/08}\newline
Beginnen aan de implementatie van de GUI a.h.v. de mock-up.
\item \textbf{14/04/08 - 20/04/08}\newline
Implementatie van de interpolatie-algoritmes, B\'ezier en Hermite.
Connectie leggen tussen deze algoritmes en de toolbar en het tekengebied.
\item \textbf{21/04/08 - 27/04/08}\newline
Beginnen aan de implementatie van de datastuctuur voor het opslaan van curves en punten.
Beginnen aan de implementatie van FileIO m.b.v. xml.
\item \textbf{28/04/08 - 04/05/08}\newline
De implementaties van de voorgaande week afwerken en het hele programma voldoende testen
op bugs.
\item \textbf{05/05/08 - 11/05/08}\newline
Afronden van algoritmes i.v.m. curvebewerkingen en puntbewerkingen.
Implementatie van fullscreen-mode en prototype van het verslag maken.
\item \textbf{12/05/08 - 18/05/08}\newline
Afronden van het implementatiegedeelte van het project.
\item \textbf{19/05/08 - 25/05/08}\newline
Programma debuggen en verslag verder aanvullen.
\item \textbf{26/05/08 - 01/06/08}\newline
Verslag afwerken en eventueel beginnen aan PowerPoint-presentatie.
\item \textbf{02/05/08 - 08/06/08}\newline
Stressen op andere projecten en eventueel presentatie voorbereiden.
\item \textbf{09/05/08 - 15/06/08}\newline
Presentatie geven op 12/06/08.
\end{itemize}
\newpage
\section{Taakverdeling}
\begin{enumerate}
\item Sibrand Staessens:
       B\'ezier-algoritmen, CurveContainer, Editor, DrawArea, GUI
\item Sibren Polders
       Hermite-algoritmen, FileIO, Menu, ToolBar, ChoiceArea, GUI, PathSimulation
\end{enumerate}
\newpage
\section{Appendix}
\appendix
\section{Screenshots}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./mockup.png}
\caption{Mock-up}\label{mock-up}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies/start.jpg}
\caption{Curve Editor-omgeving}\label{start}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{./screenies/startMarked.jpg}
\caption{Curve Editor-omgeving, aangeduid}\label{scrTot}
\end{figure}
\newpage
\section{Planning}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.55, page=1]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=2]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=3]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=4]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=5]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=6]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=7]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=8]{./planning.pdf}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8, page=9]{./planning.pdf}
\end{figure}\newpage
\section{Referenties}
Prof. dr. F. VAN REETH, Prof. dr. P. BEKAERT, 2007-2008, Computer Graphics\newline
\url{http://en.wikipedia.org/wiki/Bezier\_curve} (Bezier)\newline
\url{http://home.scarlet.be/piet.verplancken3/bezier/node9.html} (B\'ezier)\newline
\url{http://en.wikipedia.org/wiki/Catmull-Rom\_spline} (Hermite)\newline
\url{http://java.sun.com/javase/6/docs/api/} (Java)\newline
\url{http://java.sun.com/docs/books/tutorial/uiswing/events/intro.html} (Event en Listeners)\newline
\url{http://www.w3schools.com/xml/default.asp} (XML)\newline
\url{http://www.w3schools.com/dtd/default.asp} (DTD)\newline
\url{http://www.totheriver.com/learn/xml/xmltutorial.html} (XML)\newline
\url{http://www.kde.org/} (icoontjes)\newline
\section{Handleiding}
Zie bijgevoegde handleiding.
\end{document}
